// https://leetcode.cn/problems/minimum-window-substring/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    unordered_map<char, int> cnt;

    bool check() {
        for (auto it = cnt.begin(); it != cnt.end(); it++) {
            if (it->second > 0) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
        int len = INT_MAX;

        for (char ch : t) {
            cnt[ch]++;
        }

        int left = 0, right = 0;
        int start;
        while (left < s.size() && left <= right) {
            if (check()) {
                int tmpLen = right - left;
                if (tmpLen < len) {
                    start = left;
                    len = tmpLen;
                }
            }

            if (right < s.size() && !check()) {
                if (cnt.count(s[right])) {
                    cnt[s[right]]--;
                }
                right++;
            } else {
                if (cnt.count(s[left])) {
                    cnt[s[left]]++;
                }
                left++;
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};